import copy
import random
from bisect import bisect_left

# 遗传算法
class GeneticAlgorithm:
    # 参数定义
    def __init__(self, parameter):
        # 超参数
        # goal_fun:             目标函数
        # parameter_range:      参数的约束范围（左右闭区间）
        # parameter_accuracy:   各个参数精度（总共多少种可能）
        # crossover_p:          交叉概率
        # variation_p:          变异概率
        # coding_mode:          编码方式
        # max_epoch:            最大迭代次数
        # population_size:      种群个数
        self.GoalFun = parameter["goal_fun"]  # 目标函数 默认找最大值
        self.ParameterRange = parameter["parameter_range"]  # 参数的约束范围（左右闭区间）
        self.ParameterAccuracy = parameter["parameter_accuracy"]  # 各个参数精度（总共多少种可能）
        self.CrossoverP = parameter["crossover_p"]  # 交叉概率
        self.VariationP = parameter["variation_p"]  # 变异概率
        self.CodingMode = parameter["coding_mode"]  # 编码方式
        self.MaxEpoch = parameter["max_epoch"]  # 最大迭代次数
        self.PopulationSize = parameter["population_size"]  # 种群个数
        self.fitness = []  # 适应度记录

    # 产生初始种群
    def get_InitialPopulation(self):

        ans = []  # 储存种群的列表
        for _ in range(self.PopulationSize):
            dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
            # 去除不合格的编码
            while not dna_temp.is_qualified():
                dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
            ans.append(dna_temp)
        return ans

    # 计算适应度
    def get_fitness(self, dna):
        return self.GoalFun(dna.to_nums())

    # 选择一个dna（轮盘赌）
    def choice_one_dna(self, dnas):
        # 计算适应度
        fitness = copy.deepcopy(self.fitness)
        minnum = min(fitness)  # 给每一个适应度丢减去最小的额数，使最小的数字变成0
        fitness = [num - minnum for num in fitness]  # 去掉负数

        # 累加和
        fitness_leftsum = [0]
        for num in fitness:
            fitness_leftsum.append(fitness_leftsum[-1] + num)
        rande_num = random.uniform(0, fitness_leftsum[-1])  # 产生一个随机数
        site = bisect_left(fitness_leftsum, rande_num) - 1  # 根据随机数找到dna
        return dnas[site]

    # 打印信息
    def print_Population(self, words, dnas):
        print(words)
        id = 1
        for dna in dnas:
            print(id, "编码: ", dna, "解码：", dna.to_nums())
            id += 1

        print("适应度分别为:")
        print(' '.join(map(str, self.fitness)))

    # 开始迭代
    def go(self, log=False):
        # log 为真打印日志，否则不打印
        Epoch = 1
        InitialPopulation = self.get_InitialPopulation()  # 产生初始种群

        # 打印初始种群
        if log:
            self.print_Population("初始种群为", InitialPopulation)

        parents = InitialPopulation # 父代种群
        self.fitness = [self.get_fitness(dna) for dna in parents]  # 初始适应度
        while Epoch <= self.MaxEpoch:

            Crossover_count = 0  # 交叉子代计数
            Variation_count = 0  # 变异子代计数
            if log:
                print("==================================== Epoch ", Epoch, "====================================")
                self.print_Population("父代种群:", parents)
                print()
            child = parents   # 储存子代种群dna

            # 交叉
            for dna in parents:
                # 如果可以交叉
                if random.random() < self.CrossoverP:
                    t = dna.crossover(self.choice_one_dna(parents))  # 产生一个交叉个体
                    child.append(t)
                    Crossover_count += 1
                    self.fitness.append(self.get_fitness(t))  # 加入对应的适应度

            # 变异 (所有子代都可以变异)
            for i in range(len(child)):
                dna = child[i]
                # 如果可以变异
                if random.random() < self.VariationP:
                    t = dna.variation()  # 产生一个变异个体
                    child.append(t)
                    Variation_count += 1
                    self.fitness.append(self.get_fitness(t))  # 加入对应的适应度

            # 根据适应度大小对下标排序，用于筛选下一次的种群
            choice_site = sorted(list(range(len(child))), key=lambda x: self.fitness[x], reverse=True)

            parents = []  # 选取优秀的个体存活，作为下一代的父代
            self.fitness2 = []  # 储存下一次的适应度

            # 根据下标选择新的个体
            # for i in range(self.PopulationSize):
            #     parents.append(child[choice_site[i]])
            #     self.fitness2.append(self.fitness[choice_site[i]])

            # 不选择过于相近的个体 方法1
            i = 0
            for i in range(self.PopulationSize):
                
                if len(parents) == 0 or all(child[choice_site[i]].get_difference(other) for other in child):
                    parents.append(child[choice_site[i]])
                    self.fitness2.append(self.fitness[choice_site[i]])
                else:
                    dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
                    # 去除不合格的编码
                    while not dna_temp.is_qualified():
                        dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
                    parents.append(dna_temp)
                    self.fitness2.append(self.get_fitness(dna_temp))

            # 不选择过于相近的个体 方法2
            # i = 0
            # while len(parents) < self.PopulationSize:
            #     if i >= len(choice_site):
            #         dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
            #         # 去除不合格的编码
            #         while not dna_temp.is_qualified():
            #             dna_temp = self.CodingMode(self.ParameterRange, self.ParameterAccuracy)
            #         parents.append(dna_temp)
            #         self.fitness2.append(self.get_fitness(dna_temp))
            #     elif len(parents) == 0 or all(child[choice_site[i]].get_difference(other) for other in child):
            #         parents.append(child[choice_site[i]])
            #         self.fitness2.append(self.fitness[choice_site[i]])
            #     i += 1

            self.fitness = self.fitness2
            if log:
                self.print_Population("子代种群:", parents)
                print("本次迭代产生了%d个交叉新子代，%d个变异新子代" % (Crossover_count, Variation_count))
            Epoch += 1

        #  找到最优秀的个体作为答案
        return max((dna for dna in parents), key=self.get_fitness).to_nums()


